package org.example.sward.tooffer;

/**
 * 常用的排序方法
 */
public class NumsSort {

    public static void main(String[] args) {

        // 调用
        int[] nums = { 3, 4, 1, 5, 2, 1 };


        NumsSort n=new NumsSort();
        n.sortArray(nums);

        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }


    public int[] sortArray(int[] nums){
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums,int l ,int r){
        //终止条件
        if(l >= r){
            return;
        }
        //递归划分
        int m = (l + r) / 2;
        mergeSort(nums, l, m);
        mergeSort(nums, m + 1, r);

        //合并子数组
        int[] tmp = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
            tmp[i - l] = nums[i];
        }
        //两个指针分别指向左右子数组的首个元素
        int i = 0, j = m - l + 1;
        for (int k = l; k <= r ; k++) {
            if(i == m - l + 1){
                nums[k] = tmp[j++];
            }else if(j == r - l + 1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                nums[k] = tmp[j++];
            }
        }
    }

}
